{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Cameras"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCameraCover"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #监控二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树，我们在树的节点上安装摄像头。</p>\n",
    "\n",
    "<p>节点上的每个摄影头都可以监视<strong>其父对象、自身及其直接子对象。</strong></p>\n",
    "\n",
    "<p>计算监控树的所有节点所需的最小摄像头数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/29/bst_cameras_01.png\" style=\"height: 163px; width: 138px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[0,0,null,0,0]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>如图所示，一台摄像头足以监控所有节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/29/bst_cameras_02.png\" style=\"height: 312px; width: 139px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>[0,0,null,0,null,0,null,null,0]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。\n",
    "</pre>\n",
    "\n",
    "<p><br>\n",
    "<strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>给定树的节点数的范围是&nbsp;<code>[1, 1000]</code>。</li>\n",
    "\t<li>每个节点的值都是 0。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-cameras](https://leetcode.cn/problems/binary-tree-cameras/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-cameras](https://leetcode.cn/problems/binary-tree-cameras/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,0,null,0,0]', '[0,0,null,0,null,0,null,null,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: Optional[TreeNode]) -> int:\n",
    "        # 0: 没覆盖，1: 有摄像头， 2: 覆盖        \n",
    "        result = [0]\n",
    "        if self.traversal(root, result) == 0:\n",
    "            result[0] += 1\n",
    "        return result[0]\n",
    "\n",
    "    def traversal(self, cur, result) -> int:\n",
    "            if cur is None:\n",
    "                return 2\n",
    "            \n",
    "            left = self.traversal(cur.left, result)\n",
    "            right = self.traversal(cur.right, result)\n",
    "\n",
    "            if left == 2 and right == 2:\n",
    "                return 0\n",
    "            \n",
    "            if left == 0 or right == 0:\n",
    "                result[0] += 1\n",
    "                return 1\n",
    "            \n",
    "            if left == 1 or right == 1:\n",
    "                return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# leaf, to be covered\n",
    "# parent(should place camera), covered\n",
    "# 已经被子节点的camera覆盖\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: 'TreeNode') -> 'int':\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            covered = 0 # 记录当前节点有没有被cover\n",
    "            needCam = 0\n",
    "            if not node.left and not node.right:\n",
    "                return 0\n",
    "            if node.left:\n",
    "                state = dfs(node.left)\n",
    "                if state == 0:\n",
    "                    needCam = 1\n",
    "                    #covered = 1 # 在这里修改状态量也可以不过不是很reader-firendly，在if判断里去改好了\n",
    "                elif state == 1:\n",
    "                    covered = 1\n",
    "            if node.right:\n",
    "                state = dfs(node.right)\n",
    "                if state == 0:\n",
    "                    needCam = 1\n",
    "                    #covered = 1\n",
    "                elif state == 1:\n",
    "                    covered = 1\n",
    "            if needCam:\n",
    "                self.res += 1\n",
    "                covered = 1\n",
    "                return 1\n",
    "            if covered:\n",
    "                return 2\n",
    "            return 0\n",
    "        \n",
    "        state = dfs(root)\n",
    "        #return self.res\n",
    "        return self.res + 1 if state == 0 else self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root, state):\n",
    "        if not hasattr(root, 'result'):\n",
    "            root.result = [None, None, None]\n",
    "        \n",
    "        if root.result[state] is not None:\n",
    "            return root.result[state]\n",
    "        \n",
    "        if state == 0:\n",
    "            result_left = self.dfs(root.left, 1) if root.left is not None else 0\n",
    "            result_right = self.dfs(root.right, 1) if root.right is not None else 0\n",
    "            result = result_left + result_right + 1\n",
    "        elif state == 1:\n",
    "            result_empty_left = self.dfs(root.left, 2) if root.left is not None else 0\n",
    "            result_empty_right = self.dfs(root.right, 2) if root.right is not None else 0\n",
    "            result_empty = result_empty_left + result_empty_right\n",
    "            \n",
    "            result_insert_left = self.dfs(root.left, 1) if root.left is not None else 0\n",
    "            result_insert_right = self.dfs(root.right, 1) if root.right is not None else 0\n",
    "            result_insert = result_insert_left + result_insert_right + 1\n",
    "            \n",
    "            result = min(result_empty, result_insert)\n",
    "        else:\n",
    "            if root.left is None and root.right is None:\n",
    "                result = 1\n",
    "            elif root.left is None:\n",
    "                result = min(self.dfs(root.right, 0), self.dfs(root.right, 1) + 1)\n",
    "            elif root.right is None:\n",
    "                result = min(self.dfs(root.left, 0), self.dfs(root.left, 1) + 1)\n",
    "            else:\n",
    "                insert_left = self.dfs(root.left, 0) + self.dfs(root.right, 2)\n",
    "                insert_right = self.dfs(root.left, 2) + self.dfs(root.right, 0)\n",
    "                insert_both = self.dfs(root.left, 0) + self.dfs(root.right, 0)\n",
    "                insert_root = self.dfs(root.left, 1) + self.dfs(root.right, 1) + 1\n",
    "                result = min(insert_left, insert_right, insert_both, insert_root)\n",
    "        \n",
    "        root.result[state] = result\n",
    "        return result\n",
    "    \n",
    "    def minCameraCover(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return min(self.dfs(root, 0), self.dfs(root, 2))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = {None:(0, 0, 0x3f3f3f3f), 0:(0x3f3f3f3f, 0, 1)}\n",
    "        def f(n, ind):\n",
    "            if n not in dp:\n",
    "                l, r = n.left, n.right\n",
    "                if l == None and r == None:\n",
    "                    n = 0\n",
    "                else:\n",
    "                    dp[n] = (min(f(l, 2) + f(r, 0), f(l, 0) + f(r, 2), \n",
    "                    f(l, 2) + f(r, 2)), min(f(l, 0), f(l, 2)) +\n",
    "                    min(f(r, 0), f(r, 2)), 1 + min(f(l, 1), f(l, 2))\n",
    "                    + min(f(r, 1), f(r, 2)))\n",
    "            return dp[n][ind]\n",
    "        return min(f(root, 0), f(root, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        root.p = None\n",
    "        self.e = []\n",
    "        self.init(root, 0)\n",
    "        res = 0\n",
    "        self.e.sort(key=lambda x: x[0])\n",
    "        while self.e:\n",
    "            e1 = set()\n",
    "            v = self.e[-1][0]\n",
    "            while self.e and self.e[-1][0] == v:\n",
    "                n, ptr = self.e.pop()\n",
    "                if ptr.val == 1:\n",
    "                    continue\n",
    "                if ptr.left and ptr.left.val == 1:\n",
    "                    continue\n",
    "                if ptr.right and ptr.right.val == 1:\n",
    "                    continue\n",
    "                if (n + 1, ptr.left) in self.e:\n",
    "                    self.e.remove((n + 1, ptr.left))\n",
    "                    res += 1\n",
    "                    ptr.val = 1\n",
    "                    continue\n",
    "                if (n + 1, ptr.right) in self.e:\n",
    "                    self.e.remove((n + 1, ptr.right))\n",
    "                    res += 1\n",
    "                    ptr.val = 1\n",
    "                    continue\n",
    "                if ptr.p is None:\n",
    "                    ptr.val = 1\n",
    "                    if (n + 1, ptr.left) in self.e:\n",
    "                        self.e.remove((n + 1, ptr.left))\n",
    "                    if (n + 1, ptr.right) in self.e:\n",
    "                        self.e.remove((n + 1, ptr.right))\n",
    "                    res += 1\n",
    "                elif ptr.p.val != 1:\n",
    "                    res += 1\n",
    "                    ptr.p.val = 1\n",
    "                    if (n - 1, ptr.p) in self.e:\n",
    "                        self.e.remove((n - 1, ptr.p))\n",
    "                    if (n, ptr.p.left) in self.e:\n",
    "                        self.e.remove((n, ptr.p.left))\n",
    "                    if (n, ptr.p.right) in self.e:\n",
    "                        self.e.remove((n, ptr.p.right))\n",
    "                    if ptr.p.p:\n",
    "                        if (n - 2, ptr.p.p) in self.e:\n",
    "                            self.e.remove((n - 2, ptr.p.p))\n",
    "                        if ptr.p.p.p:\n",
    "                            e1.add((ptr.p.p.p.n, ptr.p.p.p))\n",
    "            for j in e1:\n",
    "                self.e.insert(bisect.bisect_left([i[0] for i in self.e], j[0]), j)\n",
    "        return res\n",
    "        \n",
    "    def init(self, root, n):\n",
    "        root.n = n\n",
    "        if root.left:\n",
    "            root.left.p = root\n",
    "            self.init(root.left, n + 1)\n",
    "        if root.right:\n",
    "            root.right.p = root\n",
    "            self.init(root.right, n + 1)\n",
    "        if root.left is None and root.right is None:\n",
    "            self.e.append((root.n, root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root, ca, must_put, mem, path):\n",
    "        if not root:\n",
    "            return 0\n",
    "        real_path = str(ca) + str(must_put) + path\n",
    "        if real_path in mem:\n",
    "            return mem[real_path]\n",
    "        put_in_me, put_in_child, put_in_left_child, put_in_right_child = 2000, 2000, 2000, 2000\n",
    "        if must_put:\n",
    "            put_in_me = 1 + self.dfs(root.left, True, False, mem, path + '0') + self.dfs(root.right, True, False, mem, path + '1')\n",
    "        elif ca:\n",
    "            put_in_child = self.dfs(root.left, False, False, mem, path + '0') + self.dfs(root.right, False, False, mem, path + '1')\n",
    "            put_in_me = 1 + self.dfs(root.left, True, False, mem, path + '0') + self.dfs(root.right, True, False, mem, path + '1')\n",
    "        else:\n",
    "            put_in_me = 1 + self.dfs(root.left, True, False, mem, path + '0') + self.dfs(root.right, True, False, mem, path + '1')\n",
    "            if root.left:\n",
    "                put_in_left_child = self.dfs(root.left, False, True, mem, path + '0') + self.dfs(root.right, False, False, mem, path + '1')\n",
    "            if root.right:\n",
    "                put_in_right_child = self.dfs(root.left, False, False, mem, path + '0') + self.dfs(root.right, False, True, mem, path + '1')\n",
    "        ans = min(put_in_me, put_in_child, put_in_left_child, put_in_right_child)\n",
    "        mem[real_path] = ans\n",
    "        return ans\n",
    "            \n",
    "    \n",
    "    def minCameraCover(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        mem = {}\n",
    "        return self.dfs(root, False, False, mem, '')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            return 1\n",
    "\n",
    "        def dfs(node, index):\n",
    "            if not node:\n",
    "                return index\n",
    "            node.val = index\n",
    "            index += 1\n",
    "            index = dfs(node.left, index)\n",
    "            return dfs(node.right, index)\n",
    "\n",
    "        dfs(root, 1)\n",
    "        memo = {}\n",
    "\n",
    "        def dp(node, val, parent):\n",
    "            if not node:\n",
    "                return float('inf') if val == 1 else 0\n",
    "\n",
    "            key = (node.val, val, parent)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "\n",
    "            ans = float('inf')\n",
    "\n",
    "            if val == 1:\n",
    "                ans = 1 + min(dp(node.left, 0, 1), dp(node.left, 1, 1)) + min(dp(node.right, 0, 1), dp(node.right, 1, 1))\n",
    "            else:\n",
    "                if node.left and node.right:\n",
    "                    for a, b in [(0, 1), (1, 0), (1, 1)]:\n",
    "                        ans = min(ans, dp(node.left, a, 0) + dp(node.right, b, 0))\n",
    "                    if parent == 1:\n",
    "                        ans = min(ans, dp(node.left, 0, 0) + dp(node.right, 0, 0))\n",
    "                elif node.left:\n",
    "                    ans = dp(node.left, 1, 0)\n",
    "                    if parent == 1:\n",
    "                        ans = min(ans, dp(node.left, 0, 0))\n",
    "                elif node.right:\n",
    "                    ans = dp(node.right, 1, 0)\n",
    "                    if parent == 1:\n",
    "                        ans = min(ans, dp(node.right, 0, 0))\n",
    "                else:\n",
    "                    ans = 1 if parent == 0 else 0\n",
    "\n",
    "            memo[key] = ans\n",
    "            return ans\n",
    "\n",
    "        # print(dp(root, 0, 0))\n",
    "        # print(dp(root, 1, 0))\n",
    "        ans = min(dp(root, 0, 0), dp(root, 1, 0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def helper(node, has_in_parent, must):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            res = helper(node.left, True, False) + helper(node.right, True, False) + 1\n",
    "            if has_in_parent:\n",
    "                res = min(res, helper(node.left, False, False) + helper(node.right, False, False))\n",
    "            else:\n",
    "                if not must:\n",
    "                    if node.left:\n",
    "                        res = min(res, helper(node.left, False, True) + helper(node.right, False, False))\n",
    "                    if node.right:\n",
    "                        res = min(res, helper(node.left, False, False) + helper(node.right, False, True))\n",
    "            return res\n",
    "        return helper(root, False, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        self.num = 0\n",
    "        if self.BSF(root) == 3:\n",
    "            self.num += 1\n",
    "        return self.num\n",
    "    \n",
    "    def BSF(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 2\n",
    "        left = self.BSF(root.left)\n",
    "        right = self.BSF(root.right)\n",
    "        if left == 3 or right ==3:\n",
    "            self.num += 1\n",
    "            return 1\n",
    "        if left == 1 or right == 1:\n",
    "            return 2\n",
    "        return 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if root==None:\n",
    "                return 1\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            # 0装了，1被监测到了，2没装\n",
    "            if left==2 or right==2:\n",
    "                res += 1\n",
    "                return 0\n",
    "            elif left == 0 or right == 0:\n",
    "                return 1\n",
    "            else:\n",
    "                return 2\n",
    "\n",
    "        if dfs(root)==2: res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "\n",
    "        UNCOVERED, CAMERA, COVERED = range(3)\n",
    "        def dfs(root, res):\n",
    "\n",
    "            left = dfs(root.left, res) if root.left else COVERED\n",
    "            right = dfs(root.right, res) if root.right else COVERED\n",
    "\n",
    "            if left == UNCOVERED or right == UNCOVERED:\n",
    "                res[0] += 1\n",
    "                return CAMERA\n",
    "            elif left == CAMERA or right == CAMERA:\n",
    "                return COVERED\n",
    "            return UNCOVERED\n",
    "\n",
    "        res = [0]\n",
    "        if dfs(root, res) == UNCOVERED:\n",
    "            res[0] += 1\n",
    "        return res[0]\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# dfs: 先序遍历，从叶节点出发\n",
    "#      若子结点不存在或不需要摄像头，则记录该结点需要摄像头\n",
    "#      若子结点需要摄像头，则此处设置摄像头\n",
    "#      最后考察根节点是否需要摄像头\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        if root == None: # special case\n",
    "            return 0\n",
    "        self.ans = 0\n",
    "        if self.dfs(root) == 1:\n",
    "            self.ans += 1\n",
    "        \n",
    "        return self.ans\n",
    "    \n",
    "    # 0: has monitor or has been monitored or not exist\n",
    "    # 1: no monitor nearby but not install monitor here\n",
    "    # 2: install monitor here\n",
    "    def dfs(self, root):\n",
    "        if root == None:\n",
    "            return 0\n",
    "        l = self.dfs(root.left)\n",
    "        r = self.dfs(root.right)\n",
    "        if l == 1 or r == 1:\n",
    "            self.ans += 1\n",
    "            return 2\n",
    "        elif l == 2 or r == 2:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    " \n",
    "        #DFS\n",
    "        self.res = 0\n",
    "        if not root:\n",
    "            return 0\n",
    "        if self.dfs(root) == 0:\n",
    "           self.res += 1\n",
    "        return self.res\n",
    "    def dfs(self,root):\n",
    "        if not root:\n",
    "            return 2\n",
    "        left = self.dfs(root.left)\n",
    "        right = self.dfs(root.right)\n",
    "        if left == 0 or right == 0:\n",
    "            self.res += 1\n",
    "            return 1\n",
    "        return 2 if left == 1 or right == 1 else 0       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        def dp(node):\n",
    "            \"\"\" return deploy, watched, unwatched \"\"\"\n",
    "            if not node: return math.inf, 0, 0\n",
    "            dp_l = dp(node.left)\n",
    "            dp_r = dp(node.right)\n",
    "            \n",
    "            deploy = dp_l[2] + dp_r[2] + 1\n",
    "            watched = min(deploy, dp_l[0] + dp_r[1], dp_l[1] + dp_r[0])\n",
    "            unwatched = min(deploy, dp_l[1] + dp_r[1])\n",
    "            return deploy, watched, unwatched\n",
    "\n",
    "        return dp(root)[1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "         \n",
    "        self.res = 0\n",
    "        def lrd(node):\n",
    "            if node is None:\n",
    "                return 1 #空节点不需要被人拍也不用拍别人，直接返回被拍了就好\n",
    "            left = lrd(node.left)\n",
    "            right = lrd(node.right)\n",
    "            if left == 0 or right == 0: \n",
    "                #如果左儿子或者右儿子需要被拍，我就装个摄像机\n",
    "                self.res += 1\n",
    "                return 2        \n",
    "            if left == 2 or right == 2:\n",
    "                #如果左儿子或者右儿子装了摄像机，那我就被拍了\n",
    "                return 1\n",
    "            else:# left == 1 and right == 1:\n",
    "                #如果左儿子和右儿子都是被拍的，都没有摄像机，那我就是需要被拍的状态\n",
    "                return 0\n",
    "\n",
    "        if lrd(root) == 0:\n",
    "            ##看看根节点是不是需要被拍\n",
    "            self.res += 1\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        def dfs(root: TreeNode) -> List[int]:\n",
    "            if not root:\n",
    "                return [float(\"inf\"), 0, 0]\n",
    "            \n",
    "            la, lb, lc = dfs(root.left)\n",
    "            ra, rb, rc = dfs(root.right)\n",
    "            a = lc + rc + 1\n",
    "            b = min(a, la + rb, ra + lb)\n",
    "            c = min(a, lb + rb)\n",
    "            return [a, b, c]\n",
    "        \n",
    "        a, b, c = dfs(root)\n",
    "        return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left == 0 and right == 0:\n",
    "                node.val = 1\n",
    "            elif left == 1 or right == 1:\n",
    "                node.val = 2\n",
    "                self.ans += 1\n",
    "            else:\n",
    "                node.val = 0\n",
    "            return node.val\n",
    "        dfs(root)\n",
    "        if root.val == 1:\n",
    "            self.ans += 1\n",
    "        return self.ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        @lru_cache(None)\n",
    "        def main(root, sign):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if sign:\n",
    "                if root.left:\n",
    "                    if root.right:\n",
    "                        return min(main(root.left, False)+main(root.right, False), main(root.left, True)+main(root.right, True)+1)\n",
    "                    else:\n",
    "                        return main(root.left, False)\n",
    "                else:\n",
    "                    if root.right:\n",
    "                        return main(root.right, False)\n",
    "                    else:\n",
    "                        return 0\n",
    "            else:\n",
    "                if root.left:\n",
    "                    if root.right:\n",
    "                        return min(main(root.left, True)+main(root.right, True), main(root.left.left, True)+main(root.left.right, True)+main(root.right, False), main(root.right.left, True)+main(root.right.right, True)+main(root.left, False)) + 1\n",
    "                    else:\n",
    "                        return main(root.left.left, True)+main(root.left.right, True)+1\n",
    "                else:\n",
    "                    if root.right:\n",
    "                        return main(root.right.left, True)+main(root.right.right, True)+1\n",
    "                    else:\n",
    "                        return 1\n",
    "        return main(root, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        nodes = [[root]]\n",
    "        root.parent = None\n",
    "        while nodes[-1]:\n",
    "            child = []\n",
    "            node = nodes[-1]\n",
    "            for item in node:\n",
    "                if item.left:\n",
    "                    child.append(item.left)\n",
    "                    item.left.parent=item\n",
    "                if item.right:\n",
    "                    child.append(item.right)\n",
    "                    item.right.parent=item\n",
    "            nodes.append(child)\n",
    "        nodes.pop()\n",
    "        nodes = nodes[::-1]\n",
    "        count = 0\n",
    "        # if len(nodes) < 3:\n",
    "        #     return 1\n",
    "        for item in nodes:\n",
    "            for node in item:\n",
    "                #如果存在未被监控的左右子树，则在此节点处放置相机\n",
    "                if node.left and node.left.val==0 or node.right and node.right.val == 0:\n",
    "                    node.val = 1\n",
    "                    if node.parent:\n",
    "                        node.parent.val = 1\n",
    "                    count += 1\n",
    "                #若此节点未被监控切不存在父节点，在此节点放置相机\n",
    "                elif node.val == 0 and not node.parent:\n",
    "                    node.val = 1\n",
    "                    count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        result = 0\n",
    "        def traversal(cur):\n",
    "            nonlocal result\n",
    "            if not cur:\n",
    "                return 2\n",
    "            \n",
    "            leftbranch = traversal(cur.left)\n",
    "            rightbranch = traversal(cur.right)\n",
    "            if leftbranch == 2 and rightbranch == 2:\n",
    "                return 0\n",
    "            elif leftbranch == 0 or rightbranch == 0:\n",
    "                result += 1\n",
    "                return 1\n",
    "            elif leftbranch == 1 or rightbranch == 1:\n",
    "                return 2\n",
    "        \n",
    "        if traversal(root) == 0:\n",
    "            result += 1\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: TreeNode) -> int:\n",
    "        # Greedy Algo:\n",
    "        # 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优\n",
    "        # 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head\n",
    "        # 0: 该节点未覆盖\n",
    "        # 1: 该节点有摄像头\n",
    "        # 2: 该节点有覆盖\n",
    "        \n",
    "        result = 0\n",
    "        def traversal(curr: TreeNode) -> int:\n",
    "            nonlocal result\n",
    "            \n",
    "            if not curr: return 2\n",
    "            \n",
    "            left = traversal(curr.left)\n",
    "            right = traversal(curr.right)\n",
    "            \n",
    "            if left == 2 and right == 2:\n",
    "                return 0\n",
    "            \n",
    "            if left == 0 or right == 0:\n",
    "                result += 1\n",
    "                return 1\n",
    "            \n",
    "            if left == 1 or right == 1:\n",
    "                return 2\n",
    "            \n",
    "        if traversal(root) == 0:\n",
    "            result += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: Optional[TreeNode]) -> int:\n",
    "        # dfs函数返回 以node为根的子树 所有节点所需的最小摄像头数量 , 与官解的状态定义不同\n",
    "        # state为当前结点node的状态, 1：光源；2：非光源但是被其父结点照亮；3：非光源且未被其父结点照亮\n",
    "        # @cache\n",
    "        # def dfs(node, state):  \n",
    "        #     if not node:\n",
    "        #         # 空结点不能是光源, 返回inf, 表示无解,因为下面是min \n",
    "        #         # 如果返回0,说明空结点可以是光源, 这样叶子结点会被照亮, 不符合要求\n",
    "        #         return 0 if state != 1 else inf \n",
    "        #     if state == 1: \n",
    "        #         return dfs(node.left, 2) + dfs(node.right, 2)\n",
    "        #     elif state == 2: # node装, 不装\n",
    "        #         return min(1 + dfs(node.left, 2) + dfs(node.right, 2), dfs(node.left, 3) + dfs(node.right, 3))\n",
    "        #     else:\n",
    "        #         # 为了保证node被照亮, node, node.left, node.right至少有一个需要装\n",
    "        #         # state=3能进入到这里说明node的父结点必定没有装\n",
    "        #         t1 = dfs(node.left, 2) + dfs(node.right, 2)  # 光源装在node上\n",
    "        #         # t2, t3的+1也可以写在if state == 1那里, 只有这里会出现state=1\n",
    "        #         t2 = dfs(node.left, 1) + dfs(node.right, 3) # 光源装在node的左孩子上如果左孩子为空dfs(node.left, 1)=inf\n",
    "        #         t3 = dfs(node.left, 3) + dfs(node.right, 1) # 光源装在node的右孩子上\n",
    "        #         return 1 + min(t1, t2, t3)\n",
    "        # return dfs(root, 3) # root初始非光源且未被照亮\n",
    "\n",
    "        # 树形DP优化, 与上面相比每个节点只需访问一次, 减少了查表的过程, 与官解的状态定义不同\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return inf, 0, 0\n",
    "            l1, l2, l3 = dfs(node.left)\n",
    "            r1, r2, r3 = dfs(node.right)\n",
    "            return l2+r2, min(1+l2+r2, l3+r3), 1+min(l2+r2, l1+r3, l3+r1)\n",
    "        return dfs(root)[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "    def calNum(self,root):\n",
    "        if root is None:\n",
    "            return 2\n",
    "\n",
    "        left = self.calNum(root.left)\n",
    "        right = self.calNum(root.right)\n",
    "        if left == 2 and right == 2:\n",
    "            return 0\n",
    "        if left == 0 or right == 0:\n",
    "            self.count+=1\n",
    "            return 1\n",
    "        return 2\n",
    "\n",
    "    def minCameraCover(self, root: Optional[TreeNode]) -> int:\n",
    "        # if root.left is None and root.right is None:\n",
    "        #     return 1\n",
    "        x = self.calNum(root)\n",
    "        if x == 0:\n",
    "            self.count+=1\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class TreeNode(object):\n",
    "\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "\n",
    "        self.val = val\n",
    "\n",
    "        self.left = left\n",
    "\n",
    "        self.right = right\n",
    "\n",
    "class Solution(object):\n",
    "\n",
    "    def minCameraCover(self, root):\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        :type root: TreeNode\n",
    "\n",
    "        :rtype: int\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        dummyroot=TreeNode(left=root)\n",
    "\n",
    "        lst=[0]\n",
    "\n",
    "        def f(root):\n",
    "\n",
    "            if root==None:\n",
    "\n",
    "                return 'monitor'\n",
    "\n",
    "            l=f(root.left)\n",
    "\n",
    "            r=f(root.right)\n",
    "\n",
    "            if l=='nomonitor' or r=='nomonitor':\n",
    "\n",
    "                lst[0]+=1\n",
    "\n",
    "                return 'install'\n",
    "\n",
    "            elif l=='install' or r=='install':\n",
    "\n",
    "                return 'monitor'\n",
    "\n",
    "            else:\n",
    "\n",
    "                return 'nomonitor'\n",
    "\n",
    "        f(dummyroot)\n",
    "\n",
    "        return lst[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        result = 0\n",
    "        check = []\n",
    "\n",
    "        def traversal(root):\n",
    "\n",
    "            nonlocal result\n",
    "            print(check)\n",
    "\n",
    "            if not root:\n",
    "                return 2\n",
    "            left = traversal(root.left)\n",
    "            right = traversal(root.right)\n",
    "\n",
    "            if left == 2 and right == 2:\n",
    "                return 0\n",
    "\n",
    "            elif left == 0 or right == 0:\n",
    "                result += 1\n",
    "                return 1\n",
    "\n",
    "            elif left == 1 or right == 1:\n",
    "                return 2\n",
    "\n",
    "        if traversal(root) == 0:\n",
    "            result += 1\n",
    "\n",
    "        return result\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: Optional[TreeNode]) -> int:\n",
    "        @cache\n",
    "        def dfs(root):\n",
    "            if not root: return inf, 0, 0\n",
    "            if not root.left and not root.right: return 1, 1, 0\n",
    "            a = b = c = inf\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            a = l[2] + r[2] + 1\n",
    "            b = min(a, l[0] + r[1], r[0] + l[1])\n",
    "            c = min(b, l[1] + r[1])\n",
    "            return a, b, c\n",
    "        return dfs(root)[1]\n",
    "# f[0]上覆盖1层\n",
    "# f[0] = l[2]+r[2]+1\n",
    "# f[1] = min(f[0], l[0] + r[1], r[0] + l[1])\n",
    "# f[2] = min(f[1], l[1] + r[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: Optional[TreeNode]) -> int:\n",
    "        # 优先从叶子节点的父节点处放摄像头，使能够充分监控到上中下三层\n",
    "        # 考虑叶子节点与根节点(一个)的数量关系,优先从叶子节点向上开始遍历，每个两个节点放一个摄像头\n",
    "        # 以及遍历到空节点时，空节点的状态应该为有覆盖的状态\n",
    "        # 分为三种情况：0无覆盖，1有摄像头，2有覆盖\n",
    "        # 1.左右孩子节点无覆盖，2.左右孩子节点至少一个无覆盖，3.左右孩子节点至少有一个有摄像头\n",
    "        # 以及对于根节点情况的单独判断\n",
    "        # 这里采用递归的方法来进行运算\n",
    "        result = [0] # 记录摄像头的放置情况\n",
    "        if self.traversal(root, result) == 0:\n",
    "            # 处于根节点的判别流程中，如若根节点处于无覆盖的情况，则单独为其增添一个摄像头\n",
    "            result[0] += 1\n",
    "        return result[0]\n",
    "    \n",
    "    def traversal(self, cur: TreeNode, result: List[int]) -> int:\n",
    "        if not cur: # 遇到空节点时，保证处理逻辑将空节点赋值为有覆盖的情况\n",
    "            return 2\n",
    "        \n",
    "        # 计算左右子节点的情况\n",
    "        left = self.traversal(cur.left, result)\n",
    "        right = self.traversal(cur.right, result)\n",
    "        \n",
    "        # 左右子节点都有覆盖,不在其对应的父节点上放置摄像头，避免浪费\n",
    "        if left == 2 and right == 2:\n",
    "            return 0\n",
    "        # 左右子结点中至少有一个为无覆盖，父节点上放置摄像头完成题目要求使得所有节点全部覆盖\n",
    "        if left == 0 or right == 0:\n",
    "            result[0] += 1\n",
    "            return 1\n",
    "        # 左右子节点中至少有一个有摄像头，则当前父节点已经被覆盖的状态\n",
    "        if left == 1 or right == 1:\n",
    "            return 2\n",
    "        # 用if只是为了条件清晰方便理解，可以采用if、elif、else的形式来简化代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: Optional[TreeNode]) -> int:\n",
    "        result = 0\n",
    "        def traversal(root):\n",
    "            nonlocal result\n",
    "            if not root:\n",
    "                return 2\n",
    "            left = traversal(root.left)\n",
    "            right = traversal(root.right)\n",
    "            if left == 2 and right == 2:\n",
    "                return 0\n",
    "            elif left == 0 or right == 0:\n",
    "                result += 1\n",
    "                return 1\n",
    "            else:\n",
    "                return 2\n",
    "        if traversal(root) == 0:\n",
    "            result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minCameraCover(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return inf, 0, 0\n",
    "            l_choose, l_by_fa, l_by_children = dfs(node.left)\n",
    "            r_choose, r_by_fa, r_by_children = dfs(node.right)\n",
    "            choose = min(l_choose, l_by_fa, l_by_children) + min(r_choose, r_by_fa, r_by_children) + 1\n",
    "            by_fa = min(l_choose, l_by_children) + min(r_choose, r_by_children)\n",
    "            by_children = min(l_choose + r_by_children, l_by_children + r_choose, l_choose + r_choose)\n",
    "            return choose, by_fa, by_children\n",
    "\n",
    "        choose, _, by_children = dfs(root)\n",
    "        return min(choose, by_children)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
